\section{Preliminaries}
\label{sec:prelim}
In this section, we define the notations used in our proofs, and prove
some common lemmas for Section \ref{sec:triangulation-10p} and Section
\ref{sec:2hop-10p}.  Let $G$ denote a connected graph, $d(u)$ denote
the degree of node $u$, and $N^i(u)$ denote the set of nodes that are
at distance $i$ from $u$. Let $\delta$ denote the minimum degree of
$G$. We note that $G$, $d(u)$, and $N^i(u)$ all change with time, and
are, in fact, random variables. For any nonnegative integer $t$, we
use subscript $t$ to denote the random variable at the start of round
$t$; for example $\gf{t}$ refers to the graph at the start of round
$t$. For convenience, we list the notations in
Table~\ref{tab:notation-10p}.

\begin{table}[htp]
\caption{Notation table \label{tab:notation-10p}}
\begin{center}
\begin{tabular}{|l|l|}
\hline
Notation & description \\
\hline
$\md{t}$ & minimum degree of graph $\gf{t}$ \\
$\nei{t}{i}{u}$ & set of nodes that are at distance $i$ from $u$ in
$\gf{t}$ \\
$\abs{\nei{t}{i}{u}}$ & number of nodes in $\nei{t}{i}{u}$ \\
$\dg{t}{u}$ & degree of node $u$ in $\gf{t}$ \\
$\dgi{t}{u}{\nei{t}{i}{v}}$ & number of edges from $u$ to nodes in
$\nei{t}{i}{v}$, i.e., degree induced on $\nei{t}{i}{v}$ \\
\hline
\end{tabular}
\end{center}
\end{table}

We state two lemmas that are used in the proofs in Section
\ref{sec:triangulation-10p} and Section \ref{sec:2hop-10p}. Lemma
\ref{lem:moreneighbor-10p} gives a lower bound on the number of
neighbors within distance 4 for any node $u$ in $\gf{t}$ while Lemma
\ref{lem:couponcorollary-10p} is a standard analysis of a sequence of
Bernoulli experiments and can be proved by a direct coupon collector
argument or using a Chernoff bound.  
%The proofs are included in Appendix~\ref{app:prelim} for completeness.

\begin{lemma}
\label{lem:moreneighbor-10p}
$\abs{\cup_{i=1}^4 \nei{t}{i}{u}} \ge \min\cub{2\md{t},n-1}$ for all
$u$ in $\gf{t}$.
\end{lemma}
\begin{proof}
  If $\nei{t}{3}{u}$ is not an empty set, consider a node $v\in
  \nei{t}{3}{u}$. Since $\dg{t}{v} \ge \md{t}$, we have that
  $\abs{\cup_{i=2}^4 \nei{t}{i}{u}} \ge
  \md{t}$. It furthermore holds that $\abs{\nei{t}{1}{u}}\ge \md{t}$ because $\dg{t}{u}\ge
  \md{t}$. We also know $\nei{t}{1}{u}$ and $\cup_{i=2}^4
  \nei{t}{i}{u}$ are disjoint. Thus, $\abs{\cup_{i=1}^4 \nei{t}{i}{u}}
  \ge 2\md{t}$.
  
  If, on the other hand, $\nei{t}{3}{u}$ is an empty set, then
  $\nei{t}{1}{u}\cup \nei{t}{2}{u}=n-1$ because $\gf{t}$ is
  connected. Thus $\abs{\cup_{i=1}^4 \nei{t}{i}{u}} = n-1$. Combining the
  the above two cases completes the proof. 
\end{proof}

\begin{lemma}
\label{lem:couponcorollary-10p}
Consider $k$ Bernoulli experiments, in which the success probability
of the $i$th experiment is at least $i/m$ where $m \ge k$.  If $X_i$
denotes the number of trials needed for experiment $i$ to output a
success and $X=\sum_{i=1}^k X_i$, then $\prob{X>(c+1)m\ln m}$ is less
than $1/m^c$.
\end{lemma}
\begin{proof}
  Since $X$ only increases with $k$, with out loss of generality
  assume that $k = m$. Now we can view this as {\em coupon collector
    problem} \cite{upfal} where $X_{m+1-i}$ is the number of steps to
  collect the $i$th coupon. Consider the probability of not obtaining
  the $i$th coupon after $(c+1)n\ln n$ steps. This probability is
\[\rb{1-\frac{1}{n}}^{(c+1)n\ln n} < e^{-(c+1)\ln n} =
\frac{1}{n^{c+1}}\] By union bound, the probability that some coupon
has not been collected after $(c+1)n\ln n$ steps is less than
$1/n^c$. And this completes the proof of this lemma.
\end{proof}
